﻿#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string.h>
#include<stdlib.h>

struct BinNode
{
	char ch;
	struct BinNode* lChild;
	struct BinNode* rChild;
};

//3.一般不定义全局变量；
//int numLeaf = 0;
//void calculateLeafNum(struct BinNode* root)
void calculateLeafNum(struct BinNode* root, int* p)
{
	if (NULL == root)
	{
		return;
	}
	if (root->lChild == NULL && root->rChild == NULL)
	{
		//numLeaf++;
		(*p)++;
	}
	//calculateLeafNum(root->lChild);
	//calculateLeafNum(root->rChild);

	calculateLeafNum(root->lChild, p);
	calculateLeafNum(root->rChild, p);
}

int getTreeHight(struct BinNode* root)
{
	if (NULL == root)
	{
		return 0;
	}

	//5.求二叉树的左子树高度；
	int lHight = getTreeHight(root->lChild);
	//6.求二叉树的右子树高度；
	int rHight = getTreeHight(root->rChild);

	int hight = lHight > rHight ? lHight + 1 : rHight + 1;
	return hight;
}
void showBinTree(struct BinNode* root)
{
	if (NULL == root)
	{
		return;
	}
	//11.先序遍历二叉树；
	printf("12.输出二叉树的节点：%c\n", root->ch);
	showBinTree(root->lChild);
	showBinTree(root->rChild);
}
struct BinNode* copyBinTree(struct BinNode* root)
{
	if (NULL == root)
	{
		return NULL;
	}
	//8.先拷贝左子树；
	struct BinNode* lChild = copyBinTree(root->lChild);
	//9.再拷贝右子树；
	struct BinNode* rChild = copyBinTree(root->rChild);
	//10.最后拷贝根节点；
	struct BinNode* newnode = malloc(sizeof(struct BinNode));
	newnode->lChild = lChild;
	newnode->rChild = rChild;
	newnode->ch = root->ch;

	return newnode;
}
void freeBinTreeSpace(struct BinNode* root)
{
	if (NULL == root)
	{
		return;
	}
	//14.释放左子树内存；
	freeBinTreeSpace(root->lChild);
	//15.释放右子树内存；
	freeBinTreeSpace(root->rChild);

	printf("18.输出被释放的节点：%c\n", root->ch);
	//16.释放根节点内存；--- 和后序遍历差不多，左->右->根；
	free(root);
}
void testBinaryTreeProgram()
{
	struct BinNode nodeA = { 'A',NULL,NULL };
	struct BinNode nodeB = { 'B',NULL,NULL };
	struct BinNode nodeC = { 'C',NULL,NULL };
	struct BinNode nodeD = { 'D',NULL,NULL };
	struct BinNode nodeE = { 'E',NULL,NULL };
	struct BinNode nodeF = { 'F',NULL,NULL };
	struct BinNode nodeG = { 'G',NULL,NULL };
	struct BinNode nodeH = { 'H',NULL,NULL };

	nodeA.lChild = &nodeB;
	nodeA.rChild = &nodeF;

	nodeB.rChild = &nodeC;
	nodeC.lChild = &nodeD;
	nodeC.rChild = &nodeE;

	nodeF.rChild = &nodeG;
	nodeG.lChild = &nodeH;


	//1.求二叉树的叶子节点数目；
	int numLeaf = 0;
	//calculateLeafNum(&nodeA);
	calculateLeafNum(&nodeA, &numLeaf);
	printf("2.输出二叉树的叶子节点数目：%d\n", numLeaf);//3

	//4.求二叉树的高度；
	int height = getTreeHight(&nodeA);
	printf("7.输出二叉树的高度：%d\n", height);//4

	//13.拷贝二叉树；
	struct BinNode* root = copyBinTree(&nodeA);
	showBinTree(root);//A,B,C,D,E,F,G,H
	printf("------------------------------------\n");
	showBinTree(&nodeA);//A,B,C,D,E,F,G,H

	//17.下面的nodeA不能释放，因为这是栈中内存，并不是堆中开辟的内存空间；
	//freeBinTreeSpace(&nodeA);
	freeBinTreeSpace(root);//D,E,C,B,H,G,F,A
}

//main229：二叉树的高度叶子节点数目拷贝释放
int main229()
{
	testBinaryTreeProgram();

	system("pause");
	return EXIT_SUCCESS;
}